#include <iostream>
using namespace std;
template <typename T>
void insertsort(T * array,int n)
{
    T temp;
    for(int i = 1;i<n;i++)
    {
        temp = array[i];
        int j = i-1;                //j为当前元素的前一个元素
        while((j>=0)&&temp<array[j])   //如果这个元素大于前一个元素，交换
        {
            array[j+1] = array[j];      //这个元素后移动
            j--;
        }
        array[j+1] = temp;
    }
}
template <typename T>
void swap(T *array,int i,int j)
{
    T temp;
    temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}
template <typename T>
void insertsortspan(T * array,int n,int delta)
{
    int i,j;
    // 对子序列中第i个记录，寻找合适的插入位置
    for(i = delta;i<n;i+=delta)
    {
        for(j = i;j>=delta;j-=delta)//j以delta步长向前寻找逆序调整
        if(array[j]<array[j-delta])     //后面delta元素和前面j-delta逆序
            swap(array,j,j-delta);
        else break;
    }
   }
template <typename T>
void shellsort(T *array,int n)
{
    int i,delta;
    for(delta = n/2;delta>0;delta/=2)
    {
        for(i=0;i<delta;i++)
        {
            // 数组第i个元素的地址而不是array地址
            insertsortspan(&array[i],n-i,delta);
        }
    }
}
template <typename T>
void print_array(T *array,int n)
{
    for(int i=0;i<n;i++)
        cout<<array[i]<<" ";
    cout<<"\n";
}
int main() {
    int array[] = {45,34,78,12,34,32,29,64};
//    print_array(array,8);
//    insertsort(array,8);
    shellsort<int>(array,8);
    print_array(array,8);
    return 0;
}